package com.msb.平衡树;

import java.util.LinkedList;
import java.util.List;

//55min
public class Code04_PathSumII_mid {

	// 测试链接：https://leetcode.com/problems/path-sum-ii
	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;

		TreeNode(int val) {
			this.val = val;
		}
	}

	// 
	public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
		List<List<Integer>> res = new LinkedList<>();
		if (root == null) {
			return res;
		}
		List<Integer> link = new LinkedList<>();
		path(root, 0, targetSum, link, res);
		return res;
	}

	// 思路: 判断倒尾节点做相关处理
	// 细节: 要想空间复杂度低需要重复利用link, 重复利用link, 注意删一下, 就拿最简单三个节点举例, 左边用完,左边删, 保持link是干净的
	// 大坑: root.left == null然后处理右节点, 会导致两个都不为null的时候都没有走
	public void path(TreeNode root, int preSum, int targetSum, List<Integer> link, List<List<Integer>> res) {
		link.add(root.val);
		if (root.left == null && root.right == null) {
			if (root.val + preSum == targetSum) {
                List<Integer> link2 = new LinkedList<>(link);
				res.add(link2);
			}
			link.remove(link.size() - 1);
			return;
		}
		if (root.left != null) {
			path(root.left, preSum + root.val, targetSum, link, res);
		}
		if (root.right != null) {
			path(root.right, preSum + root.val, targetSum, link, res);
		}
		link.remove(link.size() - 1);
	}

//	public static void main(String[] args) {
//		TreeNode treeNode = new TreeNode(1);
//		TreeNode treeNode2 = new TreeNode(2);
//		TreeNode treeNode3 = new TreeNode(2);
//
//		treeNode.left = treeNode2;
//		treeNode.right = treeNode3;
//
//		List<List<Integer>> lists = new Code04_PathSumII().pathSum(treeNode, 3);
//		System.out.println(lists);
//	}

}
